package my.test.datastructures.heap;

/**
 * @author LalitR
 */
public final class HeapApp {
	
	public static void main(String[] args) {
		Heap theHeap = new Heap(9);
		theHeap.insert(70); // insert 9 items
		theHeap.insert(40);
		theHeap.insert(50);
		theHeap.insert(20);
		theHeap.insert(60);
		theHeap.insert(80);
		theHeap.insert(30);
		theHeap.insert(10);
		theHeap.insert(90);
		
		theHeap.displayHeap();
		
		theHeap.remove();
		System.out.print("After remove: ");
		theHeap.displayHeap();
		
		theHeap.insert(90);
		theHeap.displayHeap();
		
		theHeap.remove();
		System.out.print("After remove: ");
		theHeap.displayHeap();
		
		theHeap.change(2, 0);
		theHeap.displayHeap();
	}
}

class Heap {
	private Node[] heapArray;
	private int maxSize; 		
	private int currentSize; // number of nodes in array
	
	public Heap(int size) {
		maxSize = size;
		currentSize = 0;
		heapArray = new Node[maxSize];
	}
	
	public boolean isEmpty() {
		return (currentSize == 0);
	}
	
	public boolean insert(int key) {
		if (currentSize ==  maxSize)
			return false;
		
		Node newNode = new Node(key);
		heapArray[currentSize] = newNode; // put it at the end
		trickleUp(currentSize++);
		return true;
	}
	
	public void trickleUp(int index) {
		int parent = (index -1)/2;	// parent's index
		
		Node bottom = heapArray[index]; // keep a copy of node at index
		
		while (index > 0 
				&& heapArray[parent].getKey() < bottom.getKey()) {
			heapArray[index] = heapArray[parent]; // move parent node down
			index = parent; 					  // move index up
			parent = (parent-1) / 2; 			  // parent <- its parent
		}
		heapArray[index] = bottom;
	}
	
	public Node remove() {
		Node root = heapArray[0]; 				 // keep a copy of root
		heapArray[0] = heapArray[--currentSize]; // root <- last (last node becomes root)
		trickleDown(0); 
		return root; 
	}
	
	public void trickleDown(int index) {
		int largerChild;
		Node top = heapArray[index]; // keep a copy of node at index
		
		while(index < currentSize/2) { // while node has at least one child
			int leftChild = 2*index + 1;
			int rightChild = leftChild + 1;
			
			if (rightChild < currentSize && // (i.e. rightChild exists?)
				heapArray[leftChild].getKey() < heapArray[rightChild].getKey()) {
				largerChild = rightChild;
			} else {
				largerChild = leftChild;
			}
			
			// top >= largerChild?
			if(top.getKey() >= heapArray[largerChild].getKey())
				break;
			
			heapArray[index] = heapArray[largerChild];
			index = largerChild; // go down
		}
		heapArray[index] = top; // index <- root
	}
	
	/**
	 * Change the priority (the key) of a node and then
	 * trickle it up or down to its correct position
	 */
	public boolean change(int index, int newValue) {
		if (index < 0 || index >= currentSize)
			return false;
		
		int oldValue = heapArray[index].getKey();
		heapArray[index].setKey(newValue);
		
		if (oldValue < newValue)
			trickleUp(index); 	
		else
			trickleDown(index);

		return true;
	}
	
	public void displayHeap() {
		System.out.print("heapArray: "); // array format
		for (int m = 0; m < currentSize; m++)
			if (heapArray[m] != null)
				System.out.print(heapArray[m].getKey() + " ");
			else
				System.out.print("--");
		System.out.println();
	}
}

class Node {
	int key; 			// data used as key value

	public Node(int dd) {
		this.key = dd;
	}

	/**
	 * @return the key
	 */
	public int getKey() {
		return key;
	}

	/**
	 * @param key the key to set
	 */
	public void setKey(int key) {
		this.key = key;
	}
}